/*
 * @lc app=leetcode.cn id=327 lang=golang
 *
 * [327] 区间和的个数
 */

// @lc code=start
// 使用动态规划，至底向上的对于前缀和的差值进行计算
func countRangeSum(nums []int, lower int, upper int) int {
	n := len(nums)
	prefixSum := make([]int, n+1)
	for i, v := range nums {
		prefixSum[i+1] = prefixSum[i] + v
	}

	res := 0
	// fmt.Println(nums)
	dfs(&prefixSum, 0, n+1, upper, lower, &res)
	// fmt.Println(nums)
	return res
}

func dfs(nums *[]int, left, right, upper, lower int, res *int) {
	if left >= right-1 {
		return
	}
	mid := (left + right) / 2
	dfs(nums, left, mid, upper, lower, res)
	dfs(nums, mid, right, upper, lower, res)
	merge(nums, left, mid, right, upper, lower, res)
}

func merge(nums *[]int, left, mid, right, upper, lower int, res *int) {
	// fmt.Println(*res)
	l, r := mid, mid
	for i := left; i < mid; i++ {
		// 遍历数组 直到 达到条件 N2-N1>=LOWER
		for l < right && (*nums)[l]-(*nums)[i] < lower {
			l++
		}
		// 遍历数组 直到 达到终止条件 N2-N1>UPPER
		for r < right && (*nums)[r]-(*nums)[i] <= upper {
			r++
		}
		// 此时 LOWER<=N1+N2<=UPPER
		if r <= right && l <= right && r >= l {
			*res += r - l
		}
		// *res += r - l
		// fmt.Println("------------", l, r, right, nums, *res)

	}
	l = left
	r = mid
	tmp := make([]int, 0)
	for l < mid && r < right {
		if (*nums)[l] < (*nums)[r] {
			tmp = append(tmp, (*nums)[l])
			l++
		} else {
			tmp = append(tmp, (*nums)[r])
			r++
		}
	}
	if l < mid {
		tmp = append(tmp, (*nums)[l:mid]...)
	}
	if r < right {
		tmp = append(tmp, (*nums)[r:right]...)
	}
	copy((*nums)[left:right], tmp)
}

// @lc code=end
